#include <cstdio>

const int Digit = 100000000;

struct BigNum
{
    long long num[ 300 ];
    int len;
    BigNum( ) { num[ 0 ] = 0; len = 1; }
};

struct Matrix
{
    BigNum a[ 4 ][ 4 ];
};

void Sum( BigNum &a, BigNum &b )
{
    int i;
    for ( i = a.len; i < b.len; i++  )
        a.num[ i ] = 0;
    if ( a.len < b.len )
        a.len = b.len;
    for ( i = 0; i < b.len; i++ )
    {
        a.num[ i ] += b.num[ i ];
        if ( a.num[ i ] >= Digit )
        {
            if ( i == a.len - 1 )
            {
                a.len++;
                a.num[ i + 1 ] = 0;
            }
            a.num[ i + 1 ]++;
            a.num[ i ] -= Digit;
        }
    }
    while ( i < a.len && a.num[ i ] >= Digit )
    {
        if ( i == a.len - 1 )
        {
            a.len++;
            a.num[ i + 1 ] = 0;
        }
        a.num[ i + 1 ]++;
        a.num[ i ] -= Digit;
    }
}

void Multi( BigNum &a, BigNum &b, BigNum &c )
{
    int i, j;
    c.len = a.len + b.len - 1;
    for ( i = 0; i < c.len; i++ )
        c.num[ i ] = 0;
    for ( i = 0; i < b.len; i++ )
        for ( j = 0; j < a.len; j++ )
            c.num[ i + j ] += a.num[ j ] * b.num[ i ];
    for ( i = 0; i < c.len; i++ )
        if ( c.num[ i ] >= Digit )
        {
            if ( i == c.len - 1 )
            {
                c.len++;
                c.num[ i + 1 ] = 0;
            }
            c.num[ i + 1 ] += c.num[ i ] / Digit;
            c.num[ i ] %= Digit;
        }
    while ( ( !c.num[ c.len - 1 ] ) && c.len > 1 )
        c.len--;
}

Matrix operator * ( Matrix &a, Matrix &b )
{
    Matrix c;
    int i, j, k;
    BigNum t;
    for ( i = 0; i < 4; i++ )
        for ( j = 0; j < 4; j++ )
            for ( k = 0; k < 4; k++ )
            {
                Multi( a.a[ i ][ k ], b.a[ k ][ j ], t );
                Sum( c.a[ i ][ j ], t );
            }
    return c;
}

int main( )
{
    Matrix a, b, c;
    int i, j, p, n;
    for ( i = 0; i < 4; i++ )
        b.a[ i ][ 0 ].num[ 0 ] = 1;
    b.a[ 0 ][ 1 ].num[ 0 ] = b.a[ 1 ][ 2 ].num[ 0 ] = b.a[ 2 ][ 3 ].num[ 0 ] = 1;
    while ( scanf("%d", &n) != EOF )
    {
        n--;
        for ( i = 0; i < 4; i++ )
            for ( j = 0; j < 4; j++ )
            {
                a.a[ i ][ j ].num[ 0 ] = 0;
                a.a[ i ][ j ].len = 1;
            }
        for ( i = 0; i < 4; i++ )
            a.a[ 0 ][ i ].num[ 0 ] = 1;
        p = 1;
        while ( p <= n )
            p <<= 1;
        p >>= 2;
        c = b;
        while ( p )
        {
            c = c * c;
            if ( p & n )
                c = c * b;
            p >>= 1;
        }
        a = a * c;
        printf("%I64d", a.a[ 0 ][ 3 ].num[ a.a[ 0 ][ 3 ].len - 1 ]);
        for ( i = a.a[ 0 ][ 3 ].len - 2; i >= 0; i-- )
            printf("%08I64d", a.a[ 0 ][ 3 ].num[ i ]);
        printf("\n");
    }
    return 0;
}
